As a group signature using a bilinear map, a group signature described in Non-patent Document 1 can be exemplified. The group signature disclosed in Non-patent Document 1 will be described with reference to FIG. 1.
Group secret key 1007 is assumed to be an element γ of a field Z/pZ selected at random where p is any prime number.
Group public key 1001 is assumed to be composed of:
the prime number p,
a character string that describes:
group 1, group 2, and group T whose order is p;
a bilinear map e from group 1 and group 2 to group T;
a homomorphism map φ from group 2 to group 1; and
a hash function Hash that maps a character string to the field (Z/pZ),
a generator G2 of group 2,
a generator G1 of group 1 where φ (G2)=G1,
an element 11 of group 1 selected at random, andW=[γ]G2.
In this case, W is a point γ times G2.
Secret key for tracing 1018 is assumed to be composed of two points on the field Z/pZ selected at random, ζ1 and ζ2.
Public key for tracing 1002 is assumed to be composed of two points on group 2 where [ξ1]U=[ξ2]V=H.
Member secret key 1009 is assumed to be a point x on the field Z/pZ selected at random.
Member certificate 1008 is assumed to be composed of point y on the field Z/pZ selected at random and A where A=[1/(γ+y)]([1−x]G1). Member secret key 1009 and member certificate 1008 are generated by member certificate—member secret key generation device 1005.
In the following, group signature device 1013 will be described.
Message 1012 that will be signed, group public key 1001, public key for tracing 1002, member secret key 1009, member certificate 1008, and a random number are input to group signature device 1013.
Group signature device 1013 selects points α and β on Z/pZ at random using the input random number. Thereafter, group signature device 1013 generatesT1=[α]UT2=[β]VT3=[α+β]H+A 
that form member proof's encryption text 1020.
Group signature device 1013 also selects the points α′ and β′, δ1 and δ′2, and y′ on Z/pZ at random using the input random number. Thereafter, group signature device 1013 generatesR1=[α′]UR2=[β′]VR3=e(T3,G2)^(x′)·e(H,W)^(−α′−β′)·e(H,G2)^(−δ′1−δ′2)·e(H,G2)^(y′)R4=[x′]T1−[Δ′1]U R5=[x′]T2−[Δ′2]V 
that forms a commitment,
where symbol “^” means a modular exponentiation.
Group signature device 1013 generates a hash value of group public key 1001, public key for tracing 1002, message 1012, U, V, T1, T2, T3, R1, R2, R3, R4, and R5 and treats the result as challenge value c.
Group signature device 1013 generatessα=α′+cαsβ=β′+cβsx=x′+cx sδ1=δ′1+cxαsδ2=δ′2+cxβsy=y′+xy 
that form a response.
Group signature device 1013 outputs T1, T2, T3, c, sα, sβ, sx, sδ1, sδ2, and sy as group signature 1014 to m that is message 1012.
In the following, group signature verification device 1015 will be described.
Message 1012 that has been signed, group public key 1001, and public key for tracing 1002 are input to group signature verification device 1015.
Group signature verification device 1015 generatesR1=[sα]U−[c]T1 R2=[sβ]V−[c]T2 R3=e(T3,G2)^(sx)·e(H,W)^(−sα−sβ)·e(H,G2)^(−sδ1−sδ2)·e(H,G2)^(sy)·(e(G1,G2)/e(T3,W))^(−c)R4=[sx]T1−[sδ1]U R5=[sx]T2−[sδ2]U. 
Thereafter, group signature verification device 1015 generates a hash value of group public key 1001, public key for tracing 1002, message 1012 that has been signed, U, V, T1, T2, T3, R1, R2, R3, R4, and R5 and checks whether the hash value matches challenge value c. When they match, group signature verification device 1015 determines that the group signature is valid; when they do not match, it determines that the group signature is invalid.
In the following, tracing device 1017 will be described.
Group signature 1014 that includes member proof's encryption text 1020 and secret key for tracing 1018 are input to tracing device 1017.
Tracing device 1017 computes A=T3−[ζ1]T1−[ζ2]T2 that is member proof 1019.
Tracing device 1017 identifies a user who has A, which is member proof 1019, in a member certificate as a fraudulent person.